Để chọn những học sinh có tố chất lập trình tham gia đội tuyển HSG môn Tin của trường, cô Minh đưa ra một bài tập như sau: "Có n số tự nhiên khác nhau, các em hãy viết chương trình chọn k số bất kỳ (0 < k \(\le\) n) có trong dãy sao cho tổng bằng m".
Chú ý: các cách chọn là hoán vị của nhau chỉ tính là 1 cách.
Ví dụ: m = 10, với cách chọn 3 số 4, 5, 1 chúng ta có các cách chọn như sau:
4 + 5 + 1 = 4 + 1 + 5 = 5 + 4 + 1 = 5 + 1 + 4 = 1 + 4 + 5 = 1 + 5 + 4 = 10.
Tất cả các cách trên được tính là một cách.
Dữ liệu vào từ file DOEM.inp bao gồm:
- Dòng đầu tiên ghi hai số n, m cách nhau một khoảng trắng \(\left(0< n\le100,0< m\le2.10^9\right)\).
- Dòng thứ hai ghi n số, mỗi số cách nhau một khoảng trắng.
Dữ liệu ra file DOEM.out: ghi số lượng cách chọn k số thoả điều kiện.
Ví dụ:
| DOEM.inp | DOEM.out |
5 10 | 2 |
8 23 | 0 |
Giải thích:
- Với 5 số: 4, 7, 5, 1, 3 có 2 cách chọn là: 4 + 5 + 1 = 7 + 3 = 10.
- Với 8 số: 4, 2, 6, 8, 10, 40, 20, 30 không có cách chọn thoả điều kiện.
